//
// Created by 86138 on 2025/6/25.
//

#include "SelectionSort.h"

namespace sweetcookie10_3 {

    void HeapAdjust(HeapType &H, int s, int m, Boolean flag) {
        // 已知H.base[s-m]中记录的关键字除H.base[s].key之外均满足堆的定义，
        // 本函数调整H.base[s]的关键字，使H.base[s-m]中记录的关键字均满足堆的定义
        int j;
        H.base[0] = H.base[s];
        for (j = 2 * s; j <= m; j *= 2) {
            if (flag) { // 大顶堆
                if (j < m && H.base[j].key < H.base[j + 1].key) {
                    j++;
                }
                if (H.base[0].key >= H.base[j].key) {
                    break; // 不必再调整，跳出循环
                }
            } else { // 小顶堆
                if (j < m && H.base[j].key > H.base[j + 1].key) {
                    j++;
                }
                if (H.base[0].key <= H.base[j].key) {
                    break; // 不必再调整，跳出循环
                }
            }
            H.base[s] = H.base[j];
            s = j; // 交换元素后，继续往叶子节点方向调整
        }
        H.base[s] = H.base[0]; //将待调整的记录插入[s]，注意这里的s和13行的s的值可能已经不同了
    }

    void HeapSort(HeapType &H, Boolean flag) {
        int i;
        for (i = H.length / 2; i >= 1; i--) {
            HeapAdjust(H, i, H.length, flag); // 不是从根开始筛选，而是从n/2个元素开始
        } // end for 这个for循环结束后，堆建成了

        for (i = H.length; i > 1; i--) {
            // 步骤1：交换堆顶（H.base[1]）与当前末尾元素（H.base[i]）
            H.base[0] = H.base[1];  // 临时保存堆顶元素
            H.base[1] = H.base[i];  // 将末尾元素移到堆顶
            H.base[i] = H.base[0];  // 将原堆顶元素放到末尾（已排序位置）

            // 步骤2：调整剩余堆（H.base[1]到H.base[i-1]），使其重新满足堆性质
            HeapAdjust(H, 1, i - 1, flag);
        } // 最终效果是数据base被原地排序了
    }

    void Print(HeapType L)
    { int i;
        for(i=1; i<=L.length; i++)
            printf("(%d, %d)", L.base[i].key, L.base[i].otherinfo);
        printf("\n");
    }

    void InputFromFile(FILE* f, RedType &c)
    { fscanf(f, "%d%d", &c.key, &c.otherinfo);
    }
}

//using namespace sweetcookie10_3;
//
//int main() {
//    system("chcp 65001");
//
//    FILE *f;
//    HeapType m1, m2, m3;
//    int i;
//    f=fopen("D:\\playground5\\qingdao-university\\10-sort\\f9-1.txt", "r");
//    fscanf(f, "%d", &m1.length);
//    for(i=1; i<=m1.length; i++)
//        InputFromFile(f, m1.base[i]);
//    fclose(f);
//    m2=m3=m1;
//    printf("排序前：\n");
//    Print(m1);
//
//    HeapSort(m2, TRUE);
//    printf("大顶堆排序后：\n");
//    Print(m2);
//    HeapSort(m3, FALSE);
//    printf("小顶堆排序后：\n");
//    Print(m3);
//
//    return 0;
//}